The background of the present invention is described herein in the context of pay television systems, such as cable television and direct broadcast satellite (DBS) systems, that distribute a variety of program services to subscribers, but the invention is by no means limited thereto except as expressly set forth in the accompanying claims.
In the pay television industry, programmers produce programs for distribution to various remote locations. A "program" may consist of video, audio, and other related services, such as closed-captioning and teletext services. Typically, a programmer will supply these services via satellite to individual subscribers and/or cable television operators. In the case of cable television operators, the services transmitted via satellite are received at the operator's cable head-end installations. A cable operator typically receives programs and other services from many programmers and then selects the programs/services it wishes to distribute to its subscribers. In addition, a cable operator may insert locally produced services at the cable-head end. The selected services and locally produced services are then transmitted to the individual subscribers via a coaxial cable distribution network. In the case of DBS subscribers, each subscriber is capable of receiving a satellite down-link from the programmers directly.
In the past, pay television systems, including cable and DBS systems, have operated in the analog domain. Recently, however, the pay television industry has begun to move toward all digital systems wherein, prior to transmission, all analog signals are converted to digital signals. Digital signal transmission offers the advantage that digital data can be processed at both the transmission and reception ends to improve picture quality. Further, digital data compression techniques have been developed that achieve high signal compression ratios. Digital compression allows a larger number of individual services to be transmitted within a fixed bandwidth. Bandwidth limitations are imposed by both satellite transponders and coaxial cable distribution networks, and therefore digital compression is extremely advantageous. Further background on digital television can be found in U.S. patent application Ser. No. 968,846, Oct. 30, 1992, titled System and Method for Transmitting a Plurality of Digital Services, which is hereby incorporated by reference as if fully set forth herein.
FIG. 1 schematically depicts a portion of a digital television system. This system comprises an encoder 10, a digital channel 12, and a decoder 14. The encoder and decoder each have access to identical Huffman lookup tables (or code books) 16 for use in compressing and decompressing digital program data. Exemplary program data is represented by the sequence of numbers 18 at the input of the encoder 10 and the output of the decoder 14. The compressed data (sequence of codewords) is represented by the sequence of bit patterns 20. Huffman coding is a variable length coding (VLC) process that encodes frequent events with fewer bits than it encodes infrequent events. As illustrated in the following table (which is also shown in FIG. 1), variable length codewords are preassigned to the symbols representable in the system in accordance with a Huffman code.
______________________________________ HUFFMAN TABLE Symbol Codeword ______________________________________ 0 0 -1 100 -2 101 +2 110 -3 11100 +1 11101 +7 11110 ______________________________________
In a digital video system, identical code books, typically stored in read only memory, are employed at the data encoder and decoder locations. The decoder is able to separate the received codewords to perform the decompression process, despite the fact that the codewords are of variable lengths, because only prescribed symbols are allowed. For example, if the bits "0100101" were received, the decoder would be able to separate this received data stream into the codewords "0", "100", and "101". Typically, a synchronization pattern is employed to separate large groups of codewords. However, the decoder still must be able to separate the individual codewords between the synchronization patterns.
Thus, the most efficient compression is obtained when variable length coding (VLC) is used. However, because of the variable codeword lengths, if a single bit error occurs, the Huffman decoder will lose synchronization and be unable to recover any data following the error. For example, if the data stream "0100101" were changed to "1100101" due to an erroneous inversion of the first bit, the decoder would be unable to decide whether the received data stream should be interpreted as "1100", "101" (two distinct codewords), or "110", "0", "101" (three distinct codewords). In view of the problems associated with decoding variable length codewords in most real world environments, where bit errors are likely, forward error correction (FEC) should be employed to detect and correct errors before Huffman coding is performed. For example, the Reed-Solomon algorithm is a well known FEC technique whereby parity data is computed and transmitted with data blocks of a prescribed length. The parity data enables the decoder to detect and correct errors in the codewords before decompressing the codewords to recover the original data.
Theft is also a serious problem in the pay television world. Thieves have been known to illegally decode program data with home made or stolen decoders. Highly sophisticated encryption techniques for scrambling the program data before it is distributed to cable television operators and individual subscribers are known. For example, the Data Encryption Standard (DES), described in NBS, Data Encryption Standard (FIPS Publication 46), National Bureau of Standards, U.S. Department of Commerce, Washington, D.C. (January, 1977)), and the Rivest-Shamir-Adleman (RSA) scheme, described in R. L. Rivest, A. Shamir, and L. Adleman, A Method of Obtaining Digital Signatures and Public-key Cryptosystems, Communications of the ACM 21(2), pp. 120-126 (February, 1978)), are well known. However, decryption of high speed data requires complex, specially designed circuitry, usually in the form of application specific integrated circuits (ASICs). The ASICs are expensive but are needed to perform decryption rapidly, in real time. Therefore, the benefit gained by employing encryption to deter program theft is offset by the cost incurred by the decryption circuitry.
Accordingly, a primary goal of the present invention is to provide methods and apparatus for encrypting digital data streams in a manner that enables decryption in real time with inexpensive hardware.